package 剑指offer;

public class Offer45_JZ32 {
    public String PrintMinNumber(int [] numbers) {
        int length = numbers.length;
        String[] strNums = new String[length];
        for(int i=0; i<length; i++) {
            strNums[i] = String.valueOf(numbers[i]);
        }
        quickSort(strNums, 0, length-1);
        StringBuilder strs = new StringBuilder();
        for(String str : strNums) {
            strs.append(str);
        }
        return strs.toString();
    }

    public void quickSort(String[] strNums, int start, int end) {
        if(start < end) {
            int middle = partition(strNums, start, end);
            quickSort(strNums, start, middle-1);
            quickSort(strNums, middle+1, end);
        }
    }

    public int partition(String[] strNums, int start, int end) {
        String pivot = strNums[start];
        while(start < end) {
            while(start<end && (strNums[end]+pivot).compareTo(pivot+strNums[end])>=0) {
                end--;
            }
            strNums[start] = strNums[end];
            while(start<end && (strNums[start]+pivot).compareTo(pivot+strNums[start])<=0) {
                start++;
            }
            strNums[end] = strNums[start];
        }
        strNums[start] = pivot;
        return start;
    }
}
